package com.cat.gridChart;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/shortest-path-in-a-grid-with-obstacles-elimination/
 * @create 2025/9/8 11:41
 * @since JDK17
 */

public class Solution18 {
    static int[][] q = new int[100010][2], d = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public int shortestPath(int[][] grid, int k) {
        int n = grid.length, m = grid[0].length, ans = 0, t = 0, h = 0;
        if (n == 1 && m == 1) {
            return 0;
        }
        boolean[][] vis = new boolean[n][m];
        int[][] check = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(check[i], -1);
        }
        check[0][0] = k;
        q[t++] = new int[]{0, 0, k};
        while (h < t) {
            ans++;
            for (int end = t; h < end; h++) {
                var p = q[h];
                for (int i = 0; i < 4; i++) {
                    int nx = p[0] + d[i][0], ny = p[1] + d[i][1], nk = p[2];
                    if (nx == -1 || ny == -1 || nx == n || ny == m || (grid[nx][ny] == 1 && nk <= 0)) {
                        continue;
                    }
                    if (nx == n - 1 && ny == m - 1) {
                        return ans;
                    }
                    nk -= grid[nx][ny];
                    if ((check[nx][ny] == -1) || (check[nx][ny] < nk)) {
                        check[nx][ny] = nk;
                        q[t++] = new int[]{nx, ny, nk};
                    }
                }
            }
        }

        return -1;
    }
}
